1. Field of the Invention
This invention relates to technology of image data compression, particularly to an image encoding system which performs compression encoding of multivalued input image data and an image decoding system which converts compressed encoded data back into its original form, and an image encoding method and an image decoding method.
2. Description of Related Art
Generally volumes of image data are so huge that it is often compressed to reduce its volume for communications or storage. Image encoding methods are broadly classified into two types: a reversible type and an irreversible type. In irreversible encoding methods, visual deterioration in the quality of decoded images may occur depending on the compression rate.
On the other hand, if a reversible encoding method, in which encoded data is converted into its original form to produce the same image as an input image, is used, the problem of image quality deterioration can be prevented. A technique specially designed for CG (computer graphics) images as disclosed in Japanese Published Unexamined Patent Application No. Hei 9-224253 will be explained next as a typical reversible encoding method based on the related art.
This related art example takes advantage of the characteristic of CG images that they are highly predictable when prediction is based on peripheral pixels; encoding is done on one among multiple predictors that has made the right prediction. FIGS. 14 and 15 show an example of a conventional image encoding system and of a conventional image decoding system, respectively. In these figures, 10 represents an image input unit, 20 a first predictor, 21 a second predictor, 30 a prediction error calculator, 31 a prediction error adder, 40 and 41 first selectors, 50 a second encoder, 51 a second decoder, 60 a code output unit, 70 a code input unit, 80 an image output unit, 100 image data, 110 prediction data, 111 control data, 120 prediction error data, 130 prediction condition data, 140 code data, 1010 a first predictive converter and 1020 a first predictive inverse converter.
First, the elements of the image encoding system shown in FIG. 14 are explained. The system is configured and designed to work as follows: first the image input unit 10 receives input image data from outside and sends it to the first predictor 20, the second predictor 211 and the prediction error calculator 30.
The first predictor 20 and the second predictor 21 predict the pixel value of a target pixel according to image data 100 in a given manner and sends the prediction data 110 to the first selector 40.
The prediction error calculator 30 predicts the pixel value of a target pixel in a given manner from the image data 100 and subtracts the predicted value from the real pixel value of the target pixel to send the resulting value (difference) as prediction error data 120 to the first selector 40.
The first selector 40 uses the image data 100 and the prediction data 110 to detect whether the prediction for the target pixel is right or wrong. As a result, if the prediction made by either predictor is right, the predictor's ID number is sent to the second encoder 50; if neither predictor has made the right prediction, the prediction error data 120 is converted into prediction condition data 130 and sent to the second encoder 50.
The second encoder 50 encodes the prediction condition data 130 using a given encoding technique and sends the resulting data as code data 140 to the code output unit 60. The code output unit 60 outputs the code data 140 as output code to outside.
Next, the elements of the image decoding system as shown in FIG. 15 are explained. The elements which are the same as the ones used in the image encoding system as shown in FIG. 14 are marked with the same reference numerals and their descriptions are omitted here. The code input unit 70 receives input code data from outside and sends it as code data 140 to the second decoder 51.
The second decoder 51 decodes the code data 140 using a decoding technique to match the encoding technique used in the second encoder 50 and sends the decoded data as prediction condition data 130 to the first selector 41.
If the prediction condition data 130 indicates a predictor ID number, the first selector 41 sends control data 111 to the predictor corresponding to the ID number, from which image data 100 is outputted. On the other hand, if the prediction condition data 130 indicates a prediction error, the first selector sends it as prediction error data 120 to the prediction error adder 31.
The prediction error adder 31 predicts the pixel value of the target pixel in the same way as the prediction error calculator 30, adds the prediction error data 120 to the predicted value and sends the resulting data as image data 100 to the image output unit 80. The image output unit 80 outputs the image data 100 as output image data to outside.
Next given is a description of operation in a related art example based on the above-mentioned configuration. FIG. 16 is a flowchart showing the operational sequence for a conventional image encoding system, and FIG. 17 is a flowchart showing the operational sequence for a conventional image decoding system.
First, the operational sequence for encoding is explained referring to FIG. 16. At step S10′, image data is inputted in the image input unit 10. At step S20′, the first predictor 20 and the second predictor 21 predict the pixel value of the target pixel according to the image data 100 and at the same time the prediction error calculator 30 calculates the prediction error for the predicted value in a given manner.
At step S30′, the first selector 40 sends either the ID number of the predictor whose prediction is found right or prediction error data, as prediction condition data 130, to the second encoder 50. At step S40′, the second encoder 50 performs encoding of the prediction condition data 130 in a given manner. At step S50′, the encoded data is outputted. At step S60′, if all the image data has been processed, the encoding sequence is ended; if not, the steps from S10′ are repeated.
Next, the decoding sequence is explained, referring to FIG. 17. At step S110′, code data is inputted in the code input unit 70. At step S120′, the second decoder 51 performs the decoding process which is the inverse of the encoding process which has been carried out in the second encoder 50, and generates prediction condition data 130.
At step S130′, if the prediction condition data 130 indicates a predictor ID number, the first selector 41 sends control data 111 to a predictor which has that ID number (either the first predictor 20 or the second predictor 21). If the prediction condition data 130 indicates a prediction error, the first selector 41 sends it as prediction error data 120 to the prediction error adder 31.
At step S21′, the predictor which has received the control data 111 (either the first predictor 20 or the second predictor 21) performs prediction processing in a given manner or the prediction error adder 31 adds the prediction error data 120 to the predicted value in the same manner as the prediction error calculator 30, to generate image data 100.
At step S140′, the image output unit 80 outputs the image data 100 to outside. At step S150′, if all the input code data has been processed, the decoding sequence is ended; if not, the steps from S110′ are repeated.
In the above-mentioned sequences, predictor selection at step S30′ may be made by ranking the predictors beforehand or by updating the ranking of predictors. In addition, predictor identification based on the prediction condition data 130 may be expressed by this ranking. Also, the second encoder 50 may use run length code data for the ID number of the first predictor 20.
However, the related art has the following problems. According to the related art, it is desirable for the predictors 20 and 21 to use pixels similar to the target pixel, because due to the nature of images, pixels of an identical pixel value have a tendency to concentrate spatially or come close to each other. This nature is provisionally called image locality.
There is a type of images with periodicity, called “halftone images.” “Halftone images” here refer to images which have multivalued tones as expressed in binary form or by limited tones because of the limitations of the image reproduction technique. The term “periodicity” used here is explained next.
For instance, since printing presses or inkjet printers can only represent two values by presence and absence of ink, to reproduce images, they use a publicly known technique for multivalue-binary conversion such as a systematic dither method described in Takagi and Shimoda, “HANDBOOK OF IMAGE ANALYSES”, UNIVERSITY OF TOKYO PRESS, pp. 497-498, 1991. Images produced in this way are halftone images as defined here.
In the systematic dither method, an input image is divided into partial images and the pixel value of each partial image is compared with the threshold predetermined for the coordinates of each partial image and classified into either black or white depending on whether it is larger or smaller than the threshold. Hereinafter, such partial images are called dither patterns.
In binarized image data as mentioned above, if there is a succession of equal or similar pixel values, a black and white pattern whose size is the same as a dither pattern is generated. Usually, a dither pattern uses a 4-by-4 or 8-by-8 matrix, so resulting binarized images have periodicity over multiple pixels.
FIGS. 18A and 18B show examples of a multivalued image with a uniform pixel value processed using a spiral 4-by-4 systematic dither. FIG. 18A represents a multivalued image and FIG. 18B represents a binary image produced by dithering. These phenomena often appear as a result of binarization of multivalued images or tone-limited conversion; they are not unique to systematic dither methods.
Images with periodicity as illustrated here are difficult to encode efficiently by a conventional method based on the related art. The reason is that many pixels which are unpredictable from pixels adjacent to the target pixel are generated.
The above-mentioned difficulty is illustrated next. FIG. 19 shows prediction condition data 130 which is generated when the examples of FIGS. 18A and 18B are processed according to the related art. Although prediction condition data 130 actually takes the form of a data stream, it is represented here two-dimensionally for a better understanding.
Also, it is assumed here that in the related art, the first predictor 20 serves as a “left” predictor which references a pixel just on the left of the target pixel and the second predictor 21 serves as an “above” predictor which references a pixel just above the target pixel. In the figures, “L” (left) or “A” (above) indicates a pixel which can be predicted by the “left” predictor or the “above” predictor. “E” (error) represents a pixel which cannot be predicted by either predictor.
If in the conventional method, the second encoder 50 incorporates a part which runs length encoding, there are successions of equal prediction condition data 130 in the first and the fourth line so the data can be compressed efficiently. On the other hand, data in the second and the third line have a cyclic pattern, but its compressibility is low in the conventional method.
One method to prevent such a decrease in compressibility is to add as a new predictor the fourth pixel before the target pixel. However, this method has the following problems.
1. Only a dither which corresponds to the predictor position can be used.
2. Since the number of predictors increases, the volume of prediction condition data 130 also increases and thus the compressibility decreases.
3. The increase in the number of predictors makes prediction processing more complicated and thus decreases the processing speed.
As discussed so far, the major problem of the related art is that it is impossible to compress an image with periodicity efficiently because pixels adjacent to the target pixel are mainly used for prediction processing. Furthermore, in order to prevent this, many predictors must be added, which also contributes to the problem of efficiency reduction.